package solution.s_206;

/**
 * 递归实现
 * 通过定义一个虚拟头节点
 * 然后遍历之前的链表，依次将每个节点放到虚拟头节点之后
 * 便可实现链表的反转
 */
public class Solution20220307 {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 使用一个新的虚拟头节点
        ListNode newHead = new ListNode();
        return reverseList(newHead, head).next;
    }

    private ListNode reverseList(ListNode newHead, ListNode head) {
        if (head == null) {
            return newHead;
        }

        // 保留当前节点
        ListNode curNode = head;
        // 头指针指向下一个节点
        head = head.next;

        // 将当前节点插入到虚拟头节点之后
        curNode.next = newHead.next;
        newHead.next = curNode;
        // 继续处理下一个节点
        return reverseList(newHead, head);
    }
}